1. Field of the Invention
This invention relates to digital systems, and more particularly, to methods and apparatus for providing switch matrices formed using a lesser number of switching devices than in prior art switch matrices while maintaining almost all routing paths previously available in full connection matrices.
2. History of the Prior Art
Switch matrices allow combinations of signals appearing on a large number of input signal conductors to be provided at a more limited number of output conductors. Essentially, a switch matrix comprises a first set of input conductors each of which may carry a binary input value and a second set of output conductors. The input conductors may be selectively joined to the set of output conductors by switching devices. In this manner, selective combinations of a typically large number of input signals may be furnished to a smaller number of output conductors. In a full connection matrix, any one of the input conductors may be selectively joined to each of the output conductors.
Switch matrices are used for many purposes in computer and other digital systems. For example, switch matrices are an essential part of field programmable logic arrays (PLAs). Field programmable logic arrays may be used in digital systems to provide particular logic operations using binary input signals. A PLA includes a switch matrix the output conductors of which are connected to gates which allow a plurality of input values to be manipulated in accordance with various Boolean functions. By connecting the input conductors to various AND gates and the outputs of the AND gates (product terms) to various OR gates, a particular Boolean function which is the sum of the product terms produced by the AND gates may be furnished at the output of any OR gate. The Boolean output function provided at the output of each of the OR gates is programmable by a user by programing the connections to be made by the switching devices between the input conductors and the output conductors of the switch matrix using devices such as electrically programmable read only memory (EPROM) cells, fuses, or flash EEPROM cells. Normally, a switching matrix is manufactured with the switching devices in place; and a user programs the switching devices necessary to provide the proper connections for the functions the user desires. In a full connection matrix, the number of steps required to program the switching devices equals the number of output conductors so that programming is a trivial process.
Most switch matrices include physical switching devices which allow all of the input conductors to connect to all of the output conductors. The provision of switching devices at each intersection between input and output conductors causes a number of problems.
One of the problems faced by designers of switch matrices is the large amount of die area required for the actual switching devices which may make the contacts to provide the various output combinations which may be programed. In a full connection matrix where each input conductor may be connected to each output conductor, the switching devices may occupy one-quarter of the entire die area. However, with field programmable switch matrices, it has become apparent that the number of switching devices might be reduced if the appropriate connections could still be completed. Reducing the number of actual switching devices allows the die area to be reduced thereby saving expense. It also increases the speed of operation since the length of the various conductors within the matrix may be shortened.
At least two major problems arise in attempting to reduce the number of switching devices used in a switch matrix. The first problem is to determine which switching devices may be omitted by the manufacturer while still allowing a user to obtain almost all permissible combinations of signals on the input conductors at the output conductors. A combination of input signals is permissible if the number of input signals in the combination is less than or equal to the total number of output signals. The second problem is to determine the particular connections which must be made by a user during programming in order to allow those switching devices which do exist to produce a particular desired output response for a given set of input signals. This programing is no longer the trivial process it is for a full connection matrix.
Each of these problems is complicated by the fact that the more advanced switching matrices tend to be quite large. For example, one recently designed matrix provides connections from 192 input conductors to 24 output conductors. With this number of conductors and many omitted switching devices, it is extremely difficult to test a significant number of combinations of input conductors to determine which are available at the output conductors. With prior art methods of testing, to test even one combination could require on the order of 24! (the factorial of 24) programming steps. It has been estimated that it would take hundreds of years to complete tests for such a switch matrix using conventional computers and prior art methods of testing.
It is, therefore, desirable to provide new methods for rapidly and accurately deciding which switching devices should be omitted in reduced size switch matrices and to provide methods for ascertaining which switching devices a user should connect in such matrices in order to make particular input combinations produce desired output combinations.